type TopVotedCandidate struct {
	tops, times []int
}

//预处理，遍历persons,O(n)
func Constructor(persons []int, times []int) TopVotedCandidate {
	tops := []int{}
	top := -1
	voteCnt := map[int]int{-1: -1}
	for _, p := range persons {
		voteCnt[p]++
		if voteCnt[p] >= voteCnt[top] {
			top = p
		}
		tops = append(tops, top)
	}
	return TopVotedCandidate{tops, times}
}

//二分查找，O(logn)
func (this *TopVotedCandidate) Q(t int) int {
	left, right := 0, len(this.times)-1
	for left < right {
		mid := left + (right-left+1)/2
		if this.times[mid] <= t {
			left = mid
		} else {
			right = mid - 1
		}
	}
	return this.tops[right]
}

//整体复杂度，O(n)
